#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <math.h>
#define MAX_SIZE 100

bool Check(int N, int P[], int A[]);
void Insert_sort(int i, int Num[]);
void Merge_pass(int A[], int TmpA[], int N, int len);
int main()
{
    int Sort_N[MAX_SIZE], Num[MAX_SIZE], Partial_N[MAX_SIZE];
    int N, temp, len = 1, record_i, j, insert_num;
    int *TempA;
    bool flag = false;
    scanf("%d", &N);
    for (int i = 0; i < N; i++)
    {
        scanf("%d", &Num[i]);
        Sort_N[i] = Num[i];
    }
        
    for (int i = 0; i < N; i++)
        scanf("%d", &Partial_N[i]);

    //Check for Insertion
    for (int i = 1; i < N; i++)
    {
        //-------------- CASE 3
        Insert_sort(i, Num);
        flag = Check(N, Partial_N, Num);
        if (flag)
        {
            Insert_sort(++i, Num);
            break;
        }

        //-------------- CASE 2
        // insert_num = Num[i];
        // for (j = i; j > 0 && Num[j-1] > insert_num;j--)
        //     Num[j] = Num[j - 1];
        // Num[j] = insert_num;
        // flag = Check(N, Partial_N, Num);
        // if (flag)
        // {
        //     record_i = i;
        //     break;
        // }

        //-------------- CASE 1
        // int tempi = i;
        // for (int j = i - 1; j >= 0; j--)
        // {
        //     if(Num[j]>Num[tempi])
        //     {
        //         temp = Num[tempi];
        //         Num[tempi] = Num[j];
        //         Num[j] = temp;
        //         tempi = j;
        //     }
        // }
        // flag = Check(N, Partial_N, Num);
        // if (flag)
        // {
        //     record_i = i;
        //     break;
        // }
            
    }
    if(!flag)
    {
        //definitely merge

        TempA = (int *)malloc(N * sizeof(int));
        if(TempA!=NULL)//确保内存分配生效
        {
            while(len<N)
            {
                //front
                flag = Check(N, Partial_N, Sort_N);
                Merge_pass(Sort_N, TempA, N, len);
                len *= 2;
                if(flag)
                    break;
                
                //back
                flag = Check(N, Partial_N, Sort_N);
                Merge_pass(TempA, Sort_N, N, len);
                len *= 2;
                if(flag)
                    break;
            }
            free(TempA);
        }
        printf("Merge Sort\n");
        printf("%d", Sort_N[0]);
        for (int i = 1; i < N;i++)
        {
            printf(" %d", Sort_N[i]);
        }
    }
    else
    {

        printf("Insertion Sort\n");
        printf("%d", Num[0]);
        for (int i = 1; i < N;i++)
        {
            printf(" %d", Num[i]);
        }
    }

    return 0;
}

bool Check(int N, int P[], int A[])
{
    for (int i = 0; i < N;i++)
    {
        if(P[i]!=A[i])
            return false;
    }
    return true;
}
void Merge(int A[], int TmpA[], int L, int R, int R_end)
{
    int L_end = R - 1;//左边终点位置即右点
    int tmp = L;
    int NumElements = R_end - L + 1;
    while (L <= L_end && R <= R_end)
    {
        if(A[L]<=A[R])
            TmpA[tmp++] = A[L++];
        else
            TmpA[tmp++] = A[R++];
    }
    while(L<=L_end)//直接复制左边剩下的
        TmpA[tmp++] = A[L++];
    while(R<=R_end)
        TmpA[tmp++] = A[R++];
    for (int i = 0; i < NumElements; i++, R_end--)
        A[R_end] = TmpA[R_end];
}
void Merge_pass(int A[], int TmpA[], int N, int len)
{
    int i, j;
    //归并前面的
    for (i = 0; i <= N - 2 * len; i += 2 * len)
        Merge(A, TmpA, i, i + len, i + 2 * len - 1);

    //归并最后两个子列
    if(i+len<N)
        Merge(A, TmpA, i, i + len, N - 1);
    else
        for (j = i; j < N;j++)
            TmpA[j] = A[j];
}
void Insert_sort(int i, int Num[])
{
    int temp;
    for (int j = 0; j < i; j++)
    {
        if(Num[j]>Num[i])
        {
            temp = Num[i];
            Num[i] = Num[j];
            Num[j] = temp;
        }
    }
}